class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0, n = stones.size();
        for(auto& e : stones)
        {
            sum += e;
        }
 
        vector<int> dp(sum / 2 + 1, 0);
        for(int i = 1; i <= n; ++i)
        {
            for(int j = sum / 2; j >= stones[i - 1]; --j)
            {
                dp[j] = max(dp[j] , dp[j - stones[i - 1]] + stones[i - 1]) ;
            }
        }
        return sum - 2 * dp[sum / 2];
    }
};